The present invention is directed to encoders and decoders for a digital communication system, in general, and, more particularly, to apparatus and method of encoding and decoding utilizing a combination of circular trellis-coded modulation with permuted state structure and simplex signal constellation techniques for use in a digital communication system.
In a digital communication system such as shown by way of example in the block diagram schematic of FIG. 1, digital data information is provided by a source 10 in a coded information sequence to a channel encoder 14. Channel coding in encoder 14 transforms the information sequence to a sequence of code symbols called a code sequence or code word. The transformation is designed to improve communication performance by enabling the code sequence to better withstand various channel impairments, such as noise, fading, and jamming. A modulator 16 maps the code sequence to a sequence of channel symbols drawn from a predetermined signal constellation, for example. Channel symbols may be realized by analog waveforms to be transmitted by a conventional transmitter 20 over a channel which, for the purposes of this description is assumed to be a discrete memoryless channel (DMC) with additive white Gaussian noise (AWGN).
The channel symbols are received from the channel by a conventional receiver 22 and passed to a demodulator 24 which makes a definite decision (hard decision) or a quantized approximation (soft decision) for each received symbol to one of the symbols in the predetermined signal constellation. Those symbol values are fed into a channel decoder 26 to decide the code sequence and the corresponding information sequence which may be provided to an information sink. Spreading by a power spectrum spreader 30 maps the channel signals into an extended time or frequency range according to a certain mapping function before transmission. This has advantages in many aspects, such as anti-jamming Despreading by a power spectrum despreader 34 extracts the channels signals from their received spread format.
Adding a spread spectrum (SS) function to a communication system is generally done for power limited channel transmission without substantial limitation on bandwidth of the channel. Two criteria which are satisfied are first, the bandwidth of the transmitted signal should be much larger than the message bandwidth, and second, this bandwidth should be determined by some function that is independent of the message, known as PSEUDONOISE (PN), for example. Two prevalent types of SS are direct sequence (DS) and Frequency Hopping (FH). By using PN to shift the phase of a message in DS or to select the carrier frequency in FH pseudo randomly, the effect of spreading the message spectrum over a larger frequency range is achieved. Both systems can be coupled with a coded modulation scheme for transmission over a power-limited channel. Thus, coding gain and processing gain can be achieved at the same time.
In modem digital communication, the goal is to transmit data at a high rate and with low power. According to a generalization of Shannon's Theorem, one can communicate with arbitrary reliability, i.e. error probability as small as desired, so long as one does not transmit too fast. Performance of communication systems are measured by way of a Shannon graph which plots the ratio of energy per bit (Eb) over the power spectral density of background noise in the channel environment (No) along an abscissa and probability of bit error (PBE) along the ordinate. An exemplary Shannon graph plotted on a log-log scale is shown in FIG. 2. In the graph, the ratio Eb/No is a measure of energy efficiency in decibels (dB). All curves plotted on the graph will take the form of a waterfall and are commonly referred to as waterfall curves. One benchmark is a curve 40 produced by a simple form of bit-by-bit modulation which is referred to as binary phase shift keying (BPSK) which is compared to the Shannon limit curve 42 that is an idealistic standard.
The goal in the design of modem digital communication systems is to bring the associated waterfall curve as close as practically possible to the unrealizable Shannon limit curve 42. Error correction codes embedded in or redundant to the data codes assist in this process, but there is always a price to be paid as the performance is drawn closer and closer to the Shannon limit. This price includes error coding complexity which translates into higher costs and bandwidth or coding rate. As error codes become more and more complex, greater and greater computing power is needed which translates into dollars. Another price to be paid for error correcting codes is coding rate which is the ratio of data bits to total bits transmitted. For example, if for every data bit, two bits are transmitted over the channel, then a code rate of one-half is effected. Therefore, in order to transmit a data sequence with error codes, twice the bandwidth is needed than would be needed if error coding was not used. Thus, code rate translates directly into bandwidth efficiency. Thus, the error correcting capability of the system will be determined as a trade-off given the cost appropriated for the system, and the bandwidth and power requirements that the system has to operate within.
In the real world, a channel may be either power limited or bandwidth limited and there are always trade-offs to be made depending on the application with regard to the type of error correcting codes to be used and the complexity thereof. For example, in satellites or deep space probes that have a tight power budget, signals are to be transmitted with minimum possible energy per data bit in order to preserve the lifetime of the solar batteries providing power. However, antennas may be designed to accommodate very wide transmission bandwidths with little power. Therefore, in this application, it would be desirable to use an error correcting code which may be spread over a wide bandwidth, but uses as little power as possible. On the other hand, in a telephone system that has a very narrow transmission bandwidth, but has a large power capacity, an error correcting code may be chosen to have strong signal-to-noise characteristics with high code rates. Some communication systems are made more efficient by combining the coding and modulation steps into one step, like in trellis coded modulation (TCM) or block coded modulation which will become more evident from the description found herein below.
Error control coding is generally part of the channel coding in which a controlled redundancy to the information sequence is introduced to provide the transmitted code sequence with improved ability to combat error and provide a way for the receiver to detect or correct error during transmission over a noisy channel. Conventional error control codes in practice today may be divided into two general categories: block codes and convolutional codes. In block coding, the information sequence is segmented into blocks of fixed length k. The encoder transforms each block of k information symbols to a r-tuple vector known as a code word according to a certain rule defined by a generator matrix or polynomial, for example. k/r is defined as the code rate—a measure of information bits or symbols (k) per total bits or symbols (r) transmitted. Thus, (r−k) bits are the redundancy or check bits added to perform error detection or correction. The encoder encodes each k information symbols independently. Most decoding methods for block codes are algebraic operations such as syndrome decoding for linear block codes, for example. Reed-Solomon codes, which are a particular sub-set of a family of block codes referred to as BCH codes, is a commercially successful block code used in commercial and military electronic equipment today. Hamming code is another block code in frequent use.
It is understood that block codes may be made to correct as many errors as desired, but at a price, which is a deterioration of code rate. That is, adding more redundant bits increases the number of total bits r being transmitted for the same number of information bits k; thus, reducing the ratio of k/r or code rate. In addition, since the capacity or block of information bits is fixed in length, there may be much waste of resources. By way of example, suppose the system is transmitting English words of varying length with each transmission. Then, in order to ensure that all possible words are transmitted, the length of the block should be fixed to accommodate the longest word to be transmitted. Accordingly, wasted transmission capacity will result for all shorter words, especially those substantially shorter than the longest word.
Convolutional codes, on the other hand, need not use a fixed length of information bits nor do they compute a fixed number of redundant check bits to be appended thereto and thus, provide flexibility to accommodate finite words of varying length. Convolutional codes differ from block codes in that they generate redundancy bits “on-the-fly”. The encoder for generating convolutional codes contains memory so that the r-tuple encoder output at any given time depends not only on the k-tuple input at that time instance but also on the previous K-input k-tuples. K is defined as constraint length (sometimes termed as memory order or stages of a linear shift register). An (k, r, K) convolutional code can be implemented with a k-input, r-output linear sequential circuit with input memory K, with K=max1≦i≦kKi, where Ki is the number of the delay elements or stages in the ith shift register. The rate k/r has the same code rate significance as block codes. An exemplary binary (1,2,2) encoder for convolutional coding is shown in FIG. 3. The two code symbol streams V1 and V2 output from the encoder of FIG. 3 are multiplexed together. Accordingly, for every one bit of data, there are two bits output rendering a code rate of one-half.
State diagrams and trellis diagrams are frequently used to represent a convolutional code encoder. Viewing the convolutional encoder as a finite state machine driven by the information sequence results in a state diagram illustrating the state transitions related to each possible k-tuple input. FIG. 4 exemplifies a state diagram for the encoder shown in FIG. 3. The branch is labeled by the k-tuple input string together with the output code word. By extending the state diagram of FIG. 4 along the time dimension and merging the same state at the same time instance, a trellis diagram can be obtained such as that shown in FIG. 5. A node in a trellis denotes a state. A branch represents a state transition driven by a certain input information string. It is labeled by a code symbol the encoder outputs when that state transition occurs. The level of trellis at time t0 is 0, and it increases by one at each time instance. From a starting state, all the states will be reached after a certain trellis level and then a fixed trellis section prevails. This trellis section completely describes the codes. A code word corresponding to an information sequence is represented by a sequence of state transitions along the time dimension, which is named as a trellis path. Any encoder defined by a finite state machine may be represented by a trellis and referred to as a trellis encoder. A circular trellis encoder is a type of trellis encoder in which each information sequence is mapped to a circular trellis path, i.e. a path having the same starting state and ending state. This state may be any one of the states in the circular trellis and is completely determined by the information sequence itself. In addition, all information conveyed by a trellis diagram may be also recorded in a table, referred to as a state transition table. Each transition in the table indicates the next state of the transition originating from any of the total states and driven by all possible k-tuple inputs. Use of convolutional or trellis coding in communication systems presumes that the starting state is known and agreed upon between the encoder and decoder stages thereof.
In circular trellis coding, the information sequence is truncated periodically with length L to have a block structure. In order to provide the same error protection to the last information symbol, a technique called trellis termination is employed to force the encoded trellis path to satisfy the state constraint that the starting and ending states of a trellis path should be the same. Zero tailing, tail biting, and circular trellis with permuted state structure are the three ways to do this. For a trellis code, usually 0 state is assumed. 0 state corresponds to the situation that the contents of the encoder shift register are all zeros initially. Zero tailing is one method used for trellis termination in which a certain number of zeros are appended to the truncated information sequence to force the encoded trellis path to go back to 0 state. For ease of understanding, consider a binary (1, r , K) convolutional code. In this case, K zeros are needed to append. For an information sequence of length L, the resultant code is a ((L+K)r,L) block code of rate (1/r)(L/(L+K))=(1/r)(1−K/(L+K)). The term K/(L+K) is called the rate loss due to zero tailing. To reduce the rate loss, the truncation period L is generally made as long as permissible.
An alternative method that does not introduce code rate loss is tail biting. For a binary (1, r, K) encoder, the encoder is first initialized by inputting the last K information bits of the information sequence into the encoder with its output being ignored, then, is input with all L information bits and the resultant L·r output bits is taken as the code word. The last K information bits will force the encoded path to go back to the initial state of the encoder. This state is fully determined by the input data sequence itself. It is a type of circular trellis coding. The resulting code is a (L, L·r) block code of rate 1/r.
Currently, zero tailing is the dominant practical method for trellis termination because of its simplicity and the fact that many efficient decoding algorithms were developed based on this assumption. Tail biting is only used for research to associate quasi-cyclic block codes with convolutional codes in order to apply convolutional decoding algorithm to block codes. A circular trellis coding with permuted state structure was introduced recently in the Dissertation of Yung-Cheng Lo, entitled “Circular Trellis-Coded Modulation In Spread Spectrum Communications”, Ohio University, August 1997, in which the state constraint is satisfied by designing a permuted state transition table for the encoder without code rate loss or initializing the encoder.
In Lo's Dissertation referenced above, a circular trellis is denoted as T(n, D), where n is the number of exiting branches from each state. D which is called trellis depth is the number of stages needed to reach all the possible states from a starting state. The starting state of an information sequence can be any of the total states in this trellis. When the encoder accepts one q-ary information symbol at one time (this is the case for circular trellis coding with permuted state structure), n=q, i.e., the size of the information symbol alphabet. When it accepts k-tuple q-ary inputs at one time, n=qk In either case, the total number of states in this trellis is S=nD. A state transition table may be built for this type of circular trellis using Zech's logarithm operating in a Galois finite field, GF(S). Then, in GF(S), a natural (1, S−1)-type permutation maybe expressed. By properly choosing the n out of the S “(1, S−1)-type permutation” and letting each of them associate with the state transitions driven by one of the n information symbol alphabets, a state transition table is constructed that guarantees each information sequence of length L≧D+1 will be mapped to a circular trellis path. And, the starting and ending states of this path is a function of the symbols in the information sequence. No zero padding or encoder initialization is needed in this coding scheme.
Moreover, the goal of channel coding is to achieve coding gain which is defined as the reduction in the required Eb/N0 to achieve a specified error probability using the coded system versus an uncoded system, where Eb is the average bit energy of the input data, N0 is the one-sided power spectrum density of channel noise. In conventional communication systems, coding and modulation are separate processes. The coding gain is achieved at the price of bandwidth expansion by transmitting r-tuple code word instead of k-tuple data block in the same time slot. A trellis coded modulation (TCM) method combines coding and modulation into one process. Conventional TCM has been widely used in band-limited channels. With the development of spread spectrum communications, coded modulation for power-limited spread spectrum channels has become the latest research interest.
TCM was introduced to achieve coding gain without bandwidth expansion. More specifically, it combines a multilevel/phase signal constellation with a trellis coding scheme—usually a convolutional code. A larger signal constellation is used to provide the needed coding redundancy while keeping the same channel symbol rate (bandwidth) and average power as those of an uncoded system. FIG. 6 illustrates two multilevel/phase signal e constellations used by TCM, along with the corresponding uncoded system. The expanded signal set does result in reduced distance between adjacent signal points for a given signal power. However, because of the redundancy introduced by the code, this reduced distance no longer determines the error performance. Instead, the minimum Euclidean distance (ED) between all pairs of code sequences {an} and {a′n}, which the encoder can produce determines the error performance and is defined in the following equation:             d      min        =                  min                              {                          a              n                        }                    ≠                      {                          a              n              ′                        }                              ⁢                        [                                    ∑              n                        ⁢                                          d                2                            ⁢                              (                                                      a                    n                                    ,                                      a                    n                    ′                                                  )                                              ]                          1          /          2                      ,where d(an, a′n) denotes the ED between channel signals anand a′n.
If soft-decision ML decoding is used, the error-event probability Pr(e) will asymptotically approach a lower bound at high signal-to-noise ratio as expressed in the following equation:Pr(e)≧N(dmin)Q(dmin/2σn),where N(dmin) denotes the average number of error events with distance dmin, and Q(·) is the Gaussian error probability function. σn2 is the variance of the channel noise.
Therefore, assigning signal points to the coded bits (or the state transitions in a trellis codes) in a way that maximizes the minimum ED is a way to improve system performance. An assignment procedure called “mapping by set partitioning” has been devised, which can always make the maximum minimum ED larger than the minimum distance between signal points in an uncoded system with the same data rate and average power; i.e., it can always get coding gain which can be calculated as:   G  =                    (                              d            min            2                    /                      S            av                          )            coded                      (                              d            min            2                    /                      S            av                          )            uncoded      where Sav is the average signal power.
“Mapping by set partitioning” first successively partitions a channel signal constellation into subsets with increasing minimum distance between symbols in the subsets (refer to FIG. 7) and then maps the signal constellation to code bits according to the following rules: All channel symbols are assigned with equal frequency and symmetry.    1. All parallel transitions in the trellis structure are assigned the maximum possible ED.    2. All transitions diverging from or merging into a trellis state are assigned the next maximum possible ED separation.
Applying the symbol assignment rules to an 8-state trellis by way of example as shown in FIG. 8, gives (dmin)coded=2.141. Taking an uncoded 4-PSK as reference, (dmin)uncoded=1.414. Here, the coding gain for 2/3 rate coded 8-PSK is 3.6 dB.
In the CTCM with permuted state structure of the Lo Dissertation referenced above, the goal was to achieve coding gain, processing gain, and power efficiency at the same time. Orthogonal and bi-orthogonal signal constellations were researched, but they are not optimal for power limited channels. It has been shown in the Master's Thesis of Frank A. Alder, entitled “Signal Assignment and Performance of Simplex Signaling in High Dimensional Trellis-Coded Modulation”, Ohio University, August 1998, that a simplex signal set achieves the same error probability as an equally likely orthogonal set while using the minimum energy. It is considered the optimum signal set to achieve power efficiency. A simplex is a set of M signals in an N-dimensional space with N≧M−1, satisfying that for all i, j∈{1,2, . . . , M}, the cross-correlation between signals si and sj is             s      i        ·          s      j        =      {                                                      1              ,                                                          i              =              j                                                                                                            -                  1                                                  M                  -                  1                                            ,                                                          i              ≠              j                                          ,      for normalized signal energy. It can be verified that these M signals have equal distance from each other.
CTCM using simplex signaling was explored in the above referenced Alder Thesis for very small trellises. But no systematic way to build the signal constellation and the symbol assignment therefor has of yet been described. As a result, the error distance property of these codes cannot be analyzed systematically for practical use. In addition, efficient decoding has not been investigated for these codes heretofore.
There are several efficient decoding algorithms developed for conventional TCM, such as sequential decoding, threshold decoding, Viterbi decoding, and the BCJR algorithm, for example. Among them, the Viterbi algorithm, which has been shown to be a dynamic ML decoding algorithm, is the most frequently used in practice. It is optimal in the sense that it minimizes the probability of code word error. The BCJR algorithm is also considered optimal in that it minimizes the probability of symbol (or bit) error, but is much less popular than Viterbi algorithm and is almost never applied in practical systems. The reason for this is that it yields performance in terms of symbol error probability only slightly superior to the Viterbi algorithm, yet it presents a much higher complexity. Both Viterbi and BCJR algorithm require the starting state or the distribution of the starting state be known a priori. This is not the case for circular trellis coding with permuted state structure. The optimum maximum likelihood (ML) decoding for circular trellis is to run the Viterbi algorithm the number of total states times, each for one possible starting state. This is obviously not desirable for large trellis. Hence, it would be desirable to investigate the BCJR algorithm again for use in the decoding process in this case, but first, the probability of the distribution of the starting state needs to be solved. John B. Anderson and Stephen M. Hladik in their paper entitled “Tailbiting MAP Decoders”, IEEE Journal on Selected Areas in Communications, vol. 16, No. 2, February 1998, pp 297–302 (see also U.S. Pat. No. 5,721,746, Feb. 24, 1998) extended BCJR algorithm to tail biting codes and this extension is referred to as the circular BCJR algorithm.